{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.4 Difference constraints and shortest paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-1\n",
    "\n",
    "> Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-2\n",
    "\n",
    "> Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-3\n",
    "\n",
    "> Can any shortest-path weight from the new vertex $v_0$ in a constraint graph be positive? Explain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-4\n",
    "\n",
    "> Express the single-pair shortest-path problem as a linear program."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-5\n",
    "\n",
    "> Show how to modify the Bellman-Ford algorithm slightly so that when we use it to solve a system of difference constraints with m inequalities on n unknowns, the running time is $O(nm)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-6\n",
    "\n",
    "> Suppose that in addition to a system of difference constraints, we want to handle __equality constraints__ of the form $x_i = x_j + b_k$. Show how to adapt the Bellman-Ford algorithm to solve this variety of constraint system."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-7\n",
    "\n",
    "> Show how to solve a system of difference constraints by a Bellman-Ford-like algorithm that runs on a constraint graph without the extra vertex $v_0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-8 $\\star$\n",
    "\n",
    "> Let $Ax \\le b$ be a system of $m$ difference constraints in $n$ unknowns. Show that the Bellman-Ford algorithm, when run on the corresponding constraint graph, maximizes $\\sum_{i=1}^n x_i$ subject to $Ax \\le b$ and $x_i \\le 0$ for all $x_i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-9 $\\star$\n",
    "\n",
    "> Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \\le b$ of difference constraints, minimizes the quantity $(\\max\\{x_i\\} - \\min\\{x_i\\})$ subject to $Ax \\le b$. Explain how this fact might come in handy if the algorithm is used to schedule construction jobs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-10\n",
    "\n",
    "> Suppose that every row in the matrix $A$ of a linear program $Ax \\le b$ corresponds to a difference constraint, a single-variable constraint of the form $x_i \\le b_k$, or a singlevariable constraint of the form $-x_i \\le b_k$. Show how to adapt the Bellman-Ford algorithm to solve this variety of constraint system."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-11\n",
    "\n",
    "> Give an efficient algorithm to solve a system $Ax \\le b$ of difference constraints when all of the elements of b are real-valued and all of the unknowns $x_i$ must be integers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.4-12 $\\star$\n",
    "\n",
    "> Give an efficient algorithm to solve a system $Ax \\le b$ of difference constraints when all of the elements of b are real-valued and a specified subset of some, but not necessarily all, of the unknowns $x_i$ must be integers."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
